package com.entity;

import com.entity.BinaryTreeNode;

import java.util.Objects;

public class BinaryTreeBak {

    public BinaryTreeNode root;

    public BinaryTreeBak() {
        this.root = null;
    }

    //根据key查找Node,二叉搜索树的查找时间复杂度为O(logN)
    public BinaryTreeNode find(Integer key) {
        BinaryTreeNode current = root;
        //如果根节点为null,则返回null
        if (current == null) return null;
        //如果不为空则每层遍历
        while (current.getKey() != key) {
            if (key < current.getKey()) {
                //如果key小于当前key,则往左查询
                current = current.getLeftNode();
            } else {
                current = current.getRightNode();
            }
        }
        return current;
    }

    //增加Node
    public void add(Integer key, String data) {
        BinaryTreeNode node = new BinaryTreeNode(key, data);
        //如果根节点为null,则该节点为根节点
        if (root == null) {
            root = node;
            return;
        }
        BinaryTreeNode parent;
        BinaryTreeNode current = root;
        //如果当前节点不为null则进入循环
        while (true) {
            //将当前节点赋予parent方便后面使用
            parent = current;
            if (node.getKey() < current.getKey()) {
                //如果插入节点的key小于当前节点并且当前节点的左子节点为null，则将插入节点绑定为当前节点的左子节点
                current = current.getLeftNode();
                if (current == null) {
                    parent.setLeftNode(node);
                    node.setParentNode(parent);
                    return;
                }
            } else {
                //如果插入节点的key大于当前节点并且当前节点的右子节点为null，则将插入节点绑定为当前节点的右子节点
                current = current.getRightNode();
                if (current == null) {
                    parent.setRightNode(node);
                    node.setParentNode(parent);
                    return;
                }
            }
        }
    }

    //前序遍历
    public void preOrder(BinaryTreeNode node) {
        if (node != null) {
            System.out.print(node.getData() + " ");
            preOrder(node.getLeftNode());
            preOrder(node.getRightNode());
        }
    }

    //中序遍历
    public void inOrder(BinaryTreeNode node) {
        if (node != null) {
            inOrder(node.getLeftNode());
            System.out.print(node.getData() + " ");
            inOrder(node.getRightNode());
        }
    }

    //后序遍历
    public void postOrder(BinaryTreeNode node) {
        if (node != null) {
            postOrder(node.getLeftNode());
            postOrder(node.getRightNode());
            System.out.print(node.getData() + " ");
        }
    }

    //查找最小值
    public BinaryTreeNode minNode() {
        BinaryTreeNode parent = null;
        BinaryTreeNode current = root;
        while (current != null) {
            parent = current;
            current = current.getLeftNode();
        }
        return parent;
    }

    //查找最大值
    public BinaryTreeNode maxNode() {
        BinaryTreeNode parent = null;
        BinaryTreeNode current = root;
        while (current != null) {
            parent = current;
            current = current.getRightNode();
        }
        return parent;
    }

    //删除节点
    public boolean delete(Integer key) {
        BinaryTreeNode current = root;
        if (current == null) {
            return false;
        }
        while (current.getKey() != key) {
            if (key < current.getKey()) {
                //继续递归左查找节点
                current = current.getLeftNode();
            } else if (key > current.getKey()) {
                //继续递归右查找节点
                current = current.getRightNode();
            }
            if (current == null) {
                return true;
            }
        }
        int i = 0;
        if (current.getLeftNode() != null) {
            i++;
        }
        if (current.getRightNode() != null) {
            i++;
        }
        switch (i) {
            case 0:
                deleteNoChild(current);
                break;
            case 1:
                deleteOneChild(current);
                break;
            case 2:
                deleteTwoChild(current);
                break;
            default:
                System.out.println(" this is impossible !");
        }
        return false;
    }

    //删除没有子节点的节点
    private boolean deleteNoChild(BinaryTreeNode node) {
        if (node == root) {
            root = null;
            return true;
        }
        if (node != null) {
            BinaryTreeNode parentNode = node.getParentNode();
            if (node.equals(parentNode.getLeftNode())) {
                parentNode.setLeftNode(null);
            } else {
                parentNode.setRightNode(null);
            }
            return true;
        }
        return false;
    }

    //删除一个子节点的节点
    private boolean deleteOneChild(BinaryTreeNode node) {
        if (node == root) {
            if (node.getLeftNode() != null) {
                root = node.getLeftNode();
            } else {
                root = node.getRightNode();
            }
            return true;
        }
        if (node != null) {
            BinaryTreeNode parentNode = node.getParentNode();
            Boolean isLeft = node.equals(parentNode.getLeftNode()) ? true : false;
            BinaryTreeNode child = node.getLeftNode() != null ? node.getLeftNode() : node.getRightNode();
            if (isLeft) {
                //如果当前节点为父节点的左子节点,则将当前节点的左节点或者右节点绑定为父节点的左子节点(此处应以确定只有一个节点)
                parentNode.setLeftNode(child);
            } else {
                //如果当前节点为父节点的左子节点,则将当前节点的左节点或者右节点绑定为父节点的左子节点(此处应以确定只有一个节点)
                parentNode.setRightNode(child);
            }
            return true;
        }
        return false;
    }

    //删除两个子节点的节点
    private boolean deleteTwoChild(BinaryTreeNode node) {
        //先找出后继节点
        BinaryTreeNode successor = getSuccessor(node);
        if (node == root) {
            successor.setLeftNode(root.getLeftNode());
            successor.setRightNode(root.getRightNode());
            successor.setParentNode(null);
            root = successor;
        }
        BinaryTreeNode parentNode = node.getParentNode();
        //获得删除节点的左子节点
        BinaryTreeNode leftNode = node.getLeftNode();
        //获得删除节点的右子节点
        BinaryTreeNode rightNode = node.getRightNode();
        //1.设置后继节点的左子节点为删除节点的左子节点
        successor.setLeftNode(leftNode);
        //2.设置后继节点的右子节点为删除节点的右子节点
        successor.setRightNode(rightNode);
        //3.设置后继节点的父节点为删除节点的父节点
        successor.setParentNode(parentNode);
        //4.设置删除节点的父节点的左节点或者右节点为后继节点(根据删除节点是删除节点父节点的左右子节点)
        BinaryTreeNode successorParentNode = successor.getParentNode();
        BinaryTreeNode successorRightNode = successor.getRightNode();
        if (node.equals(parentNode.getLeftNode())) {
            successorParentNode.setLeftNode(successorRightNode);
            successorRightNode.setParentNode(successorParentNode);
            parentNode.setLeftNode(successor);
        } else {
            successorParentNode.setRightNode(successorRightNode);
            successorRightNode.setParentNode(successorParentNode);
            parentNode.setRightNode(successor);
        }
        //help gc
        node = null;
        return true;
    }

    private BinaryTreeNode getSuccessor(BinaryTreeNode node) {
        if (node == null) {
            return null;
        }
        BinaryTreeNode current = node.getRightNode();
        while (current != null && current.getLeftNode() != null) {
            current = current.getLeftNode();
        }
        return current;
    }

}
